
def shell_sort(alist):
    """希尔排序
    插入排序的一种
    只是将原先的直接一列插入，分组，分成不同的列插入，
    再合并，再拆分，再插入
    """
    n = len(alist)
    gap = n//2
    # gap = 3

    # [1,2,3,4,5]
    # gap = 2
    # [1,3,5]
    #  i  i+gap i+2gap
    # [2,4]
    #  i+1 i+1+gap
    while gap >= 1:
        # 插入排序
        for i in range(gap,n):
            while i>=gap:
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= gap
                else:
                    break
        gap //= 2

def insert_sort(alist):
    # 插入排序
    n = len(alist)
    for i in range(1,n):
        while i>=1:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break

alist =	[3,4,6,6,1,2,5]
# [3, 6, 2]
# [4, 1, 5]
# [
shell_sort(alist)
print(alist)

insert_sort(alist)
print(alist)

